package com.tgy.leetcode;

/**
 *
 * https://leetcode-cn.com/problems/grumpy-bookstore-owner/
 */
public class _1052_爱生气的书店老板 {

    /**
     * O(n)
     * @param customers
     * @param grumpy
     * @param X
     * @return
     */
    public static int maxSatisfied(int[] customers, int[] grumpy, int X) {

        int len = customers.length;
        int index = X - 1;
        int notAngryCustomers = 0;

        for (int i = 0; i < len; i++) {

            if (grumpy[i] == 0) {

                notAngryCustomers += customers[i];
            }
        }
        int maxCustom = 0;
        int angryCustomers = 0;
        for (int i = 0; i < len; i++) {

            if (grumpy[i] == 1) {
                angryCustomers += customers[i];
            }
            int left = i - X;
            if (left >= 0 && grumpy[left] == 1) {

                angryCustomers -= customers[left];
            }
            maxCustom = Math.max(maxCustom, notAngryCustomers + angryCustomers);
        }

        return maxCustom;
    }

    /**
     * O(n^2)
     * @param customers
     * @param grumpy
     * @param X
     * @return
     */
    public static int maxSatisfied01(int[] customers, int[] grumpy, int X) {

        int index = X - 1;
        int len = customers.length;
        int maxCustom = 0;
        while (index < len) {

            int left = index - X + 1;
            int sum = 0;
            for (int i = 0; i < len; i++) {

                if (i >= left && i <= index) {

                    sum += customers[i];
                    continue;
                }

                if (grumpy[i] == 0) {

                    sum+= customers[i];
                }
            }

            maxCustom = Math.max(maxCustom,sum);
            index++;
        }

        return maxCustom;
    }

    public static void main(String[] args) {

        //customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1]
        int[] customers = {1,0,1,2,1,1,7,5};
        int[] grumpy =    {0,1,0,1,0,1,0,1};
        int k = 3;
        System.out.println(maxSatisfied(customers, grumpy, k));
    }
}
